""" 消除游戏
在一个字符串S 中, 如果 Si = Si-1且 Si ≠ Si+1, 则称 Si 和 Si+1 为边缘字符。如果 Si ≠ Si-1且 Si = Si+1 , 则 Si 和 Si-1 也称为边缘字符。
其它的字符都不是边缘字符。

对于一个给定的串 S, 一次操作可以一次性删除该串中的所有边缘字符 (操作后可能产生新的边缘字符)。

请问经过 2的64次方 次操作后, 字符串 S 变成了怎样的字符串, 如果结果为空则 输出 EMPTY。
例如, 输入为: "edda" 输出为 EMPTY
输入: "sdfhhhhcvhhxcxnnnnshh" 输出:s
"""
from collections import deque


def erase(s):
    """超时/全部 = 7/12 6分"""
    while True:  # sdhhcnn
        n = len(s)
        remove_set = set()  # 待删除的元素索引
        for i in range(1, n - 1):
            if s[i] == s[i - 1] and s[i] != s[i + 1]:
                remove_set.add(i)
                remove_set.add(i + 1)
            if s[i] != s[i - 1] and s[i] == s[i + 1]:
                remove_set.add(i)
                remove_set.add(i - 1)

        # 重新拼接字符串
        ns = "".join(s[i] for i in range(n) if i not in remove_set)

        if not ns:  # 空字符串
            return "EMPTY"
        if len(ns) == 1:  # 只有一个字符了
            return ns
        if ns == s:  # 字符串没有变化
            return ns
        s = ns


def erase_opt(s: str) -> str:
    n = len(s)
    if n == 0:
        return "EMPTY"

    # 初始化双向链表的前驱和后继数组
    # prev[idx]表示第idx个节点的前驱指针, prev[1] = 0 表示节点1的前驱节点为0, prev[0] = -1 表示节点0没有前驱节点
    prev = list(range(-1, n - 1))
    # next_[idx]表示第idx个节点的后驱指针, next_[1] = 2 表示节点1的后驱节点为2, 如果next_[x] >= n 则表示该节点没有后驱节点
    next_ = list(range(1, n + 1))
    deleted = [False] * n  # 标记每个位置是否已删除

    def check(idx: int) -> set:
        """
        检查位置 idx 是否是边缘字符
        如果是，则返回需删除的索引集合（可能包含 idx 自己或其相邻位置）。
        条件：
          1. 如果 idx 的前驱存在且 s[idx] == s[prev[idx]]，且 idx 的后继存在且 s[idx] != s[next_[idx]]，
             则标记 idx 和其后继为待删除。
          2. 如果 idx 的前驱存在且 s[idx] != s[prev[idx]]，且 idx 的后继存在且 s[idx] == s[next_[idx]]，
             则标记 idx 和其前驱为待删除。
        """
        if deleted[idx]:
            return set()
        res = set()
        left = prev[idx]
        right = next_[idx] if next_[idx] < n else -1
        if left != -1 and right != -1:
            if s[idx] == s[left] and s[idx] != s[right]:
                res.add(idx)
                res.add(right)
            if s[idx] != s[left] and s[idx] == s[right]:
                res.add(left)
                res.add(idx)
        return res

    def remove(idx: int):
        """
        标记位置 idx 为删除，并更新链表中其前驱和后继的指针。
        """
        nonlocal prev, next_, deleted
        deleted[idx] = True
        left = prev[idx]
        right = next_[idx] if next_[idx] < n else -1
        # 更新左侧的后继指针
        if left != -1:
            next_[left] = right
        # 更新右侧的前驱指针
        if right != -1:
            prev[right] = left

    # 初始队列包含所有索引
    active = set(range(n))
    while active:
        to_delete = set()
        # 对当前所有待检查的索引进行检查
        for idx in active:
            """a |= b 是一种集合的原地并集操作，等价于 a = a | b。也就是将集合a更新为a和b的并集, 包含a和b的所有元素
            P.S. 两个集合求交集: a & b"""
            to_delete |= check(idx)

        if not to_delete:
            break  # 本轮没有删除，则结束

        new_active  = set()  # 下一轮待检查的索引集合
        # 对所有待删除的索引进行删除，并更新链表
        for idx in to_delete:
            if not deleted[idx]:
                remove(idx)
                # 将该位置左右的邻居加入下一轮待检查集合
                left = prev[idx]
                right = next_[idx] if next_[idx] < n else -1
                if left != -1:
                    new_active.add(left)
                if right != -1:
                    new_active.add(right)

        # 下一轮处理所有受影响的邻居: 删除边缘节点之后, 只有这些被删除的边缘节点的邻居有可能成为边缘节点
        active = new_active

    # 构建结果字符串：依次遍历原字符串中未删除的字符
    result = [s[i] for i in range(n) if not deleted[i]]
    return "EMPTY" if not result else "".join(result)


if __name__ == '__main__':
    # s = "abcde"
    # print(s[:1] + s[2:])
    print(erase("edda"))  # EMPTY
    print(erase("sdfhhhhcvhhxcxnnnnsh"))  # s
    print(erase_opt("edda"))  # EMPTY
    print(erase_opt("sdfhhhhcvhhxcxnnnnsh"))  # s
